
//496.下一个更大元素I
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        //先将nums2中每个位置下一个更大元素记录下来
        //从左向右：存储还没找到满足条件的位置
        int n1=nums1.size(),n2=nums2.size();
        stack<pair<int,int>> st;
        unordered_map<int,int> m;   //存储nums2中每一个位置的元素,方便nums1在nums2中的查找
        st.push({nums2[0],0});
        m[nums2[0]]=0;        

        vector<int> next(n2,-1);  
        for(int i=1;i<n2;i++)
        {
            m[nums2[i]]=i;  
            while(!st.empty()&&st.top().first<nums2[i]) //将找到满足条件的位置出栈
            {
                int index=st.top().second;
                next[index]=nums2[i];

                st.pop();
            }                
            st.push({nums2[i],i});  //入栈
        }

        vector<int> ans(n1);   
        for(int i=0;i<n1;i++)  
        {
            int index=m[nums1[i]];  //index是nums2中与nums1[i]相同的位置下标
            ans[i]=next[index];
        }
        return ans;
    }
};